package org.example.algorithm.dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class GenerateTriangleSolution {

    public static void main(String[] args) {
        GenerateTriangleSolution solution = new GenerateTriangleSolution();
        List<List<Integer>> res = solution.generate(5);
        System.out.println(res);
    }

    //使用dp数组
    //该实现是为了练习下二位数组操作
    public List<List<Integer>> generate(int numRows) {
        Integer[][] dp = new Integer[numRows][];
        for (int i=0;i<numRows;i++) {
            Integer[] row = new Integer[i+1];
            for (int j=0;j<=i;j++) {
                if (j==0 || j==i) {
                    row[j] = 1;
                } else {
                    row[j] = dp[i-1][j-1] + dp[i-1][j];
                }
            }
            dp[i] = row;
        }
        List<List<Integer>> res = new ArrayList<>();
        for (Integer[] row: dp) {
            res.add(Arrays.asList(row));
        }
        return res;
    }

    public List<List<Integer>> generate3(int numRows) {
        List<List<Integer>> list = new ArrayList<>();
        for (int i=0;i<numRows;i++) {
            List<Integer> row = new ArrayList<>();
            //第i+1行有i-0+1个数字
            for (int j=0;j<=i;j++) {
                if (j==0 || j==i) {
                    row.add(1);
                } else {
                    row.add(list.get(i-1).get(j-1) + list.get(i-1).get(j));
                }
            }
            list.add(row);
        }
        return list;
    }

        // 1
    //   1   1
    // 1   2   1
    //1  3   3  1
    //该实现较为繁琐
    public List<List<Integer>> generate2(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer>  row1 = new ArrayList<>();
        row1.add(1);
        res.add(row1);
        if (numRows == 1) {
            return res;
        }
        List<Integer>  row2 = new ArrayList<>();
        row2.add(1);
        row2.add(1);
        res.add(row2);
        if (numRows == 2) {
            return res;
        }
        List<Integer> preRow = row2;
        for (int i=3;i<=numRows;i++) {
            List<Integer> newRow = new ArrayList<>();
            newRow.add(1);
            int index = 0;
            int preNum = 0;
            for (Integer num: preRow) {
                if (index++ == 0) {
                    preNum = num;
                    continue;
                }
                newRow.add(preNum + num);
                preNum = num;
            }
            newRow.add(1);
            preRow = newRow;
            res.add(newRow);
        }
        return res;
    }
}
